// https://leetcode.cn/problems/search-insert-position/

// 题干：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
//      如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
//      请必须使用时间复杂度为 O(log n) 的算法。

// 示例：输入: nums = [1,3,5,6], target = 5
//       输出: 2

// 碎语：很明显的二分提示，查找分界线是<target | >= target
//       且要取右边的数字

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int searchInsert(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;

        while (left < right){
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        return nums[left] >= target ? left : left + 1; // 处理边界的特殊情况，若最后左右指针相遇在最后一个位置则自加
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,3,5,6};

    cout << sol.searchInsert(nums, 5) << endl;

    return 0;
}